{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ships in a Rectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countShips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩形内船只的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><em>(此题是 <strong>交互式问题&nbsp;</strong>)</em></p>\n",
    "\n",
    "<p>在用笛卡尔坐标系表示的二维海平面上，有一些船。每一艘船都在一个整数点上，且每一个整数点最多只有 1 艘船。</p>\n",
    "\n",
    "<p>有一个函数&nbsp;<code>Sea.hasShips(topRight, bottomLeft)</code>&nbsp;，输入参数为右上角和左下角两个点的坐标，当且仅当这两个点所表示的矩形区域（包含边界）内至少有一艘船时，这个函数才返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code> 。</p>\n",
    "\n",
    "<p>给你矩形的右上角&nbsp;<code>topRight</code> 和左下角&nbsp;<code>bottomLeft</code> 的坐标，请你返回此矩形内船只的数目。题目保证矩形内&nbsp;<strong>至多只有 10 艘船</strong>。</p>\n",
    "\n",
    "<p>调用函数&nbsp;<code>hasShips</code>&nbsp;<strong>超过400次&nbsp;</strong>的提交将被判为&nbsp;<em>错误答案（Wrong Answer）</em>&nbsp;。同时，任何尝试绕过评测系统的行为都将被取消比赛资格。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/30/1445_example_1.png\" style=\"height: 500px; width: 496px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>\n",
    "ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>在 [0,0] 到 [4,4] 的范围内总共有 3 艘船。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ans = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,0]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>ships</code>&nbsp;数组只用于评测系统内部初始化。你必须“蒙着眼睛”解决这个问题。你无法得知&nbsp;<code>ships</code>&nbsp;的信息，所以只能通过调用&nbsp;<code>hasShips</code>&nbsp;接口来求解。</li>\n",
    "\t<li><code>0 &lt;=&nbsp;bottomLeft[0]&nbsp;&lt;= topRight[0]&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;bottomLeft[1]&nbsp;&lt;= topRight[1]&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>topRight != bottomLeft</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ships-in-a-rectangle](https://leetcode.cn/problems/number-of-ships-in-a-rectangle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ships-in-a-rectangle](https://leetcode.cn/problems/number-of-ships-in-a-rectangle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[2,2],[3,3],[5,5]]\\n[4,4]\\n[0,0]', '[[1,1],[2,2],[3,3]]\\n[1000,1000]\\n[0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point', claim: bool=False) -> int:\n",
    "        x1, y1 = topRight.x, topRight.y\n",
    "        x2, y2 = bottomLeft.x, bottomLeft.y\n",
    "        if x1 < x2 or y1 < y2:\n",
    "            return 0\n",
    "        judge = True if claim else sea.hasShips(topRight, bottomLeft)\n",
    "        if not judge:\n",
    "            return 0\n",
    "        if (x1, y1) == (x2, y2):\n",
    "            return 1\n",
    "        if x1 == x2:\n",
    "            ymid = (y1 + y2) // 2\n",
    "            A = self.countShips(sea, Point(x1, ymid), Point(x1, y2))\n",
    "            return A + self.countShips(sea, Point(x1, y1), Point(x1, ymid + 1), A == 0)\n",
    "        else:\n",
    "            xmid = (x1 + x2) // 2\n",
    "            A = self.countShips(sea, Point(xmid, y1), Point(x2, y2))\n",
    "            return A + self.countShips(sea, Point(x1, y1), Point(xmid + 1, y2), A == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Divide and conquer:\n",
    "        Split the rectangle into 4 sub-rectangles.\n",
    "        Check if each sub-rectangle has ships, and if so, recursively count the ships in the sub-rectangle.\n",
    "    Let m, n be the width and height of the rectangle, k be the number of ships, and suppose Sea.hasShips() takes O(1) time.\n",
    "    Time complexity: O(klog(max(m, n))).\n",
    "        Explanation: Each time we split a rectangle into 4 sub-rectangles, we reduce the width and height by half.\n",
    "                     So, there could be at most log2(max(m, n)) levels of recursion.\n",
    "                     We make 4 Sea.hasShips() calls at the 1st level, 16 calls at the 2nd level, and so on.\n",
    "                     However, the max number of calls for a level is 4 * k, since at most k sub-rectangles from the previous level can progress.\n",
    "    Space complexity: O(log(max(m, n))).\n",
    "    '''\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        # check if the rectangle is valid\n",
    "        if topRight.x < bottomLeft.x or bottomLeft.y > topRight.y:\n",
    "            return 0\n",
    "        \n",
    "        # check if the rectangle has ships\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        \n",
    "        # check if the rectangle is a single point\n",
    "        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:\n",
    "            return 1\n",
    "        \n",
    "        # divide and conquer\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y)) + \\\n",
    "               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        midx = (topRight.x + bottomLeft.x) // 2\n",
    "        midy = (topRight.y + bottomLeft.y) // 2\n",
    "        if midx + 1 <= topRight.x:\n",
    "            ans += self.countShips(sea, Point(topRight.x, midy), Point(midx + 1, bottomLeft.y))\n",
    "        ans += self.countShips(sea, Point(midx, midy), bottomLeft)\n",
    "        if midy + 1 <= topRight.y:\n",
    "            ans += self.countShips(sea, Point(midx, topRight.y), Point(bottomLeft.x, midy + 1))\n",
    "        if midx + 1 <= topRight.x and midy + 1 <= topRight.y:\n",
    "            ans += self.countShips(sea, topRight, Point(midx + 1, midy + 1))\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "\n",
    "# log4(1000 * 1000) = 10 最大十层\n",
    "# 最多10个船，最坏情况下每一个子矩形都只有一艘船，任何层级最多有10个非空子矩形，10个有船只，30空的，\n",
    "# 对于每一个包含船只的子矩形，用Hasship调用，4次，所以最坏总调用数是10 * 4 * log4(1000 * 1000) = 400\n",
    "\n",
    "# 十艘船随机分布的在四个大小相等的子区域，最有可能的情况是 [3, 3, 2, 2] 的情况，也就是两个区域有 3 艘，两个区域有 2 艘。最终答案 S(10) 等于 2 * (S(3) + S(2))\n",
    "\n",
    "# 先计算区域有 3 艘的调用次数 S(3)， 3 艘船随机分布在四个大小相等的子区域，最有可能的情况是 [1, 1, 1, 0]，最后一个区域只需要调用一次即可。其他三个区域需要一直四分直到找到船，由于这时候每个区域的大小为 250，所以调用次数为 log2(250) * 4 ≈ 32 次。S(3) = 3 * 32 + 1 = 97\n",
    "\n",
    "# 同理，要计算区域有 2 艘的调用次数 S(2)， 2 艘船随机分布在四个大小相等的子区域，最有可能的情况是 [1, 1, 0, 0]，最后两个区域只需要调用一次即可。其他两个区域需要一直四分直到找到船，由于这时候每个区域的大小为 250，所以调用次数为 log2(250) * 4 ≈ 32 次。S(2) = 2 * 32 + 2 = 66\n",
    "\n",
    "# 最终计算出 S(10) = 2 * ( 97 + 66 ) = 326\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:  \n",
    "        if (bottomLeft.x > topRight.x) or (bottomLeft.y > topRight.y):\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "\n",
    "        if (topRight.x == bottomLeft.x) and (topRight.y == bottomLeft.y):\n",
    "            return 1\n",
    "\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        if bottomLeft.x > topRight.x or bottomLeft.y > topRight.y:\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:\n",
    "            return 1\n",
    "        rx = (topRight.x+bottomLeft.x)//2\n",
    "        ry = (topRight.y+bottomLeft.y) //2\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "\n",
    "        \n",
    "        # newMid = Point(rx,ry)\n",
    "        # return (self.countShips(sea,newMid, bottomLeft) + \n",
    "        # self.countShips(sea, topRight, Point(rx+1, ry+1) + \n",
    "        # self.countShips(sea,Point(rx, topRight.y), Point(bottomLeft.x, ry+1)) +\n",
    "        # self.countShips(sea, Point(topRight.x, ry), Point(rx+1, bottomLeft/y))\n",
    "        # )\n",
    "        \n",
    "        \n",
    "        # )\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "# class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        \n",
    "        def has_ship(x1, y1, x2, y2):\n",
    "            return int(sea.hasShips(Point(x2, y2), Point(x1, y1)))\n",
    "        \n",
    "        def check(x1, y1, x2, y2):\n",
    "            if x1 == x2 and y1 == y2:\n",
    "                return has_ship(x1, y1, x2, y2)\n",
    "            if not has_ship(x1, y1, x2, y2):\n",
    "                return 0\n",
    "            x0 = x1+(x2-x1)//2\n",
    "            y0 = y1+(y2-y1)//2\n",
    "            res = check(x1, y1, x0, y0)\n",
    "            if x0+1<=x2:\n",
    "                res += check(x0+1, y1, x2, y0)\n",
    "            if y0+1<=y2:\n",
    "                res += check(x1, y0+1, x0, y2)\n",
    "            if x0+1<=x2 and y0+1<=y2:\n",
    "                res += check(x0+1, y0+1, x2, y2)\n",
    "         \n",
    "            return res\n",
    "        \n",
    "        x1, y1 = bottomLeft.x, bottomLeft.y\n",
    "        x2, y2 = topRight.x, topRight.y\n",
    "\n",
    "        return check(x1, y1, x2, y2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        x1, y1 = topRight.x, topRight.y\n",
    "        x2, y2 = bottomLeft.x, bottomLeft.y\n",
    "\n",
    "        if x1 < x2 or y1 < y2 or not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        \n",
    "        if x1 == x2 and y1 == y2:\n",
    "            return 1\n",
    "\n",
    "        xmid = (x1 + x2) // 2\n",
    "        ymid = (y1 + y2) // 2\n",
    "\n",
    "        a = self.countShips(sea, Point(xmid, ymid), Point(x2, y2))\n",
    "        b = self.countShips(sea, Point(x1, ymid), Point(xmid + 1, y2))\n",
    "        c = self.countShips(sea, Point(xmid, y1), Point(x2, ymid + 1))\n",
    "        d = self.countShips(sea, Point(x1, y1), Point(xmid + 1, ymid + 1))\n",
    "\n",
    "        return a + b + c + d\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        # sea.hasShips可以帮助我们知道 topRight->bottomLeft是否有船只\n",
    "        def dfs(x1, y1, x2, y2):\n",
    "            if (x1, y1) == (x2, y2):\n",
    "                return int(sea.hasShips(Point(x2, y2), Point(x1, y1)))\n",
    "            if x1 > x2 or y1 > y2 or not sea.hasShips(Point(x2, y2), Point(x1, y1)):\n",
    "                return 0\n",
    "            x0, y0 = (x1 + x2) // 2, (y1 + y2) // 2\n",
    "            ans = 0\n",
    "            ans += dfs(x1, y1, x0, y0)\n",
    "            ans += dfs(x1, y0 + 1, x0, y2)\n",
    "            ans += dfs(x0 + 1, y0 + 1, x2, y2)\n",
    "            ans += dfs(x0 + 1, y1, x2, y0)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(bottomLeft.x, bottomLeft.y, topRight.x, topRight.y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        # 如果当前矩形不包含船，则返回 0。           \n",
    "        if (bottomLeft.x > topRight.x) or (bottomLeft.y > topRight.y):\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "\n",
    "        # 如果矩形代表一个点，则定位了一艘船\n",
    "        if (topRight.x == bottomLeft.x) and (topRight.y == bottomLeft.y):\n",
    "            return 1\n",
    "\n",
    "        # 递归地检查 4 个子矩形中的船\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        top_right_x = topRight.x\n",
    "        top_right_y = topRight.y\n",
    "        bottom_left_x = bottomLeft.x\n",
    "        bottom_left_y = bottomLeft.y\n",
    "\n",
    "        if bottom_left_x > top_right_x or bottom_left_y > top_right_y or not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "\n",
    "        if bottom_left_x == top_right_x and bottom_left_y == top_right_y:\n",
    "            return 1\n",
    "\n",
    "        mid_x = (bottom_left_x + top_right_x) >> 1\n",
    "        mid_y = (bottom_left_y + top_right_y) >> 1\n",
    "        blocks = [[Point(mid_x, top_right_y), Point(bottom_left_x, mid_y + 1)],\n",
    "                  [Point(top_right_x, top_right_y), Point(mid_x + 1, mid_y + 1)],\n",
    "                  [Point(top_right_x, mid_y), Point(mid_x + 1, bottom_left_y)],\n",
    "                  [Point(mid_x, mid_y), Point(bottom_left_x, bottom_left_y)]]\n",
    "\n",
    "        res = 0\n",
    "        for block in blocks:\n",
    "            top_right_coord = block[0]\n",
    "            bottom_left_coord = block[1]\n",
    "            res += self.countShips(sea, top_right_coord, bottom_left_coord)\n",
    "            if res == 10:\n",
    "                return res\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "\n",
    "        def dfs(tr,bl):\n",
    "            if tr.x < bl.x or tr.y < bl.y:\n",
    "                return 0\n",
    "            if not sea.hasShips(tr,bl):\n",
    "                return 0\n",
    "            if tr.x - bl.x == 0 and tr.y - bl.y == 0:\n",
    "                return 1\n",
    "            x_mid = (tr.x + bl.x)//2\n",
    "            y_mid = (tr.y + bl.y)//2\n",
    "\n",
    "            return dfs( Point(x_mid,y_mid),Point(bl.x,bl.y)) + \\\n",
    "                    dfs(Point(x_mid,tr.y), Point(bl.x,y_mid + 1)) + \\\n",
    "                    dfs(Point(tr.x,tr.y), Point(x_mid + 1,y_mid + 1)) + \\\n",
    "                    dfs(Point(tr.x,y_mid), Point(x_mid + 1,bl.y))\n",
    "        \n",
    "        return dfs(topRight,bottomLeft)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        if bottomLeft.x > topRight.x or bottomLeft.y > topRight.y:\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:\n",
    "            return 1\n",
    "        # rx = (topRight.x+bottomLeft.x)//2\n",
    "        # ry = (topRight.y+bottomLeft.y) //2\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "\n",
    "        \n",
    "        # newMid = Point(rx,ry)\n",
    "        # return (self.countShips(sea,newMid, bottomLeft) + \n",
    "        # self.countShips(sea, topRight, Point(rx+1, ry+1) + \n",
    "        # self.countShips(sea,Point(rx, topRight.y), Point(bottomLeft.x, ry+1)) +\n",
    "        # self.countShips(sea, Point(topRight.x, ry), Point(rx+1, bottomLeft/y))\n",
    "        # )\n",
    "        \n",
    "        \n",
    "        # )\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        \n",
    "        # Base Case: Check for invalid rectangle.\n",
    "        if (bottomLeft.x > topRight.x) or (bottomLeft.y > topRight.y):\n",
    "            return 0\n",
    "        \n",
    "        # Base Case: If the rectangle does not have ships.\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        \n",
    "        # Base Case: If it's a single point and has a ship.\n",
    "        if (topRight.x == bottomLeft.x) and (topRight.y == bottomLeft.y):\n",
    "            return 1\n",
    "        \n",
    "        # Compute midpoints for x and y coordinates.\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        \n",
    "        # Recursive calls for each of the four sub-rectangles.\n",
    "        bottom_left_ships = self.countShips(sea, Point(mid_x, mid_y), bottomLeft)\n",
    "        top_right_ships = self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1))\n",
    "        top_left_ships = self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1))\n",
    "        bottom_right_ships = self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "        \n",
    "        # Sum up the ships from all sub-rectangles.\n",
    "        total_ships = bottom_left_ships + top_right_ships + top_left_ships + bottom_right_ships\n",
    "        \n",
    "        return total_ships\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "\n",
    "# log4(1000 * 1000) = 10 最大十层\n",
    "# 最多10个船，最坏情况下每一个子矩形都只有一艘船，任何层级最多有10个非空子矩形，10个有船只，30空的，\n",
    "# 对于每一个包含船只的子矩形，用Hasship调用，4次，所以最坏总调用数是10 * 4 * log4(1000 * 1000) = 400\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:  \n",
    "        if (bottomLeft.x > topRight.x) or (bottomLeft.y > topRight.y):\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "\n",
    "        if (topRight.x == bottomLeft.x) and (topRight.y == bottomLeft.y):\n",
    "            return 1\n",
    "\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        if (topRight.x<bottomLeft.x) or (topRight.y<bottomLeft.y):\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "\n",
    "        # find the exact location of one ship\n",
    "        if topRight.x==bottomLeft.x and topRight.y==bottomLeft.y:\n",
    "            return 1\n",
    "\n",
    "        midx = bottomLeft.x + (topRight.x - bottomLeft.x) // 2\n",
    "        midy = bottomLeft.y + (topRight.y - bottomLeft.y) // 2\n",
    "\n",
    "        return self.countShips(sea, Point(midx, topRight.y), Point(bottomLeft.x, midy+1)) + \\\n",
    "               self.countShips(sea, topRight, Point(midx+1, midy+1)) + \\\n",
    "               self.countShips(sea, Point(midx, midy), bottomLeft) + \\\n",
    "               self.countShips(sea, Point(topRight.x, midy), Point(midx+1, bottomLeft.y))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y:\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "\n",
    "        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:\n",
    "            return 1\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2    \n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "            self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "            self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y)) + \\\n",
    "            self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x , mid_y + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        if bottomLeft.x > topRight.x or bottomLeft.y > topRight.y:\n",
    "            return 0 \n",
    "        if not sea.hasShips(topRight,bottomLeft):\n",
    "            return 0 \n",
    "        if bottomLeft.x == topRight.x and bottomLeft.y == topRight.y:\n",
    "            return 1 \n",
    "        \n",
    "        middleX = (bottomLeft.x + topRight.x) // 2\n",
    "        middleY = (bottomLeft.y + topRight.y) // 2\n",
    "        return self.countShips(sea,Point(middleX,middleY),bottomLeft) + self.countShips(sea,Point(topRight.x,middleY),Point(middleX+1,bottomLeft.y)) + self.countShips(sea,Point(middleX,topRight.y),Point(bottomLeft.x,middleY+1)) + self.countShips(sea,topRight,Point(middleX+1,middleY+1))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        # Base Case: \n",
    "        if bottomLeft.x > topRight.x or bottomLeft.y > topRight.y:\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:\n",
    "            return 1\n",
    "        \n",
    "        top_right_x = topRight.x\n",
    "        top_right_y = topRight.y\n",
    "        bottom_left_x = bottomLeft.x\n",
    "        bottom_left_y = bottomLeft.y\n",
    "        res = 0\n",
    "        mid_x = (top_right_x + bottom_left_x) // 2\n",
    "        mid_y = (top_right_y + bottom_left_y) // 2\n",
    "\n",
    "        res += self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1))\n",
    "        \n",
    "        res += self.countShips(sea, Point(mid_x, top_right_y), Point(bottom_left_x, mid_y + 1))\n",
    "        \n",
    "        res += self.countShips(sea, Point(mid_x, mid_y), bottomLeft)\n",
    "        \n",
    "        res += self.countShips(sea, Point(top_right_x, mid_y), Point(mid_x + 1, bottom_left_y))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        if bottomLeft.x > topRight.x or bottomLeft.y > topRight.y:\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y:\n",
    "            return 1\n",
    "        rx = (topRight.x+bottomLeft.x)//2\n",
    "        ry = (topRight.y+bottomLeft.y) //2\n",
    "\n",
    "        # mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        # mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        # return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "        #        self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "        #        self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "        #        self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "\n",
    "        \n",
    "        newMid = Point(rx,ry)\n",
    "        return (self.countShips(sea,newMid, bottomLeft)\n",
    "         +  self.countShips(sea, topRight, Point(rx+1, ry+1))\n",
    "          +  self.countShips(sea,Point(rx, topRight.y), Point(bottomLeft.x, ry+1))\n",
    "           + self.countShips(sea, Point(topRight.x, ry), Point(rx+1, bottomLeft.y))\n",
    "        )\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "\n",
    "\n",
    "        def binary(top_right, bottom_left):\n",
    "            x,y = top_right.x, top_right.y\n",
    "            a,b = bottom_left.x, bottom_left.y\n",
    "            if x<a or y<b:\n",
    "                return 0 \n",
    "            \n",
    "            has =  sea.hasShips(top_right,bottom_left)\n",
    "            if not has:\n",
    "                return 0 \n",
    "\n",
    "            if x==a and y==b:\n",
    "                return 1\n",
    "            \n",
    "\n",
    "            \n",
    "            midx = (x+a)//2\n",
    "            midy = (y+b)//2\n",
    "\n",
    "\n",
    "            ans = 0 \n",
    "            if x-a>=y-b:\n",
    "                if x>=midx+1 :\n",
    "                    ans += binary(Point(x,y), Point(midx+1,b))\n",
    "                if midx>=a and  sea.hasShips(Point(midx,y), Point(a,b)):\n",
    "                    ans += binary(Point(midx,y), Point(a,b))\n",
    "            \n",
    "            else:\n",
    "                if  y>=midy+1 :\n",
    "                    ans += binary(Point(x,y), Point(a,midy+1))\n",
    "\n",
    "                if  midy>=b :\n",
    "                    ans += binary(Point(x,midy), Point(a,b))\n",
    "            return ans \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        return binary(topRight,bottomLeft)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        # 如果当前矩形不包含船，则返回 0。           \n",
    "        if (bottomLeft.x > topRight.x) or (bottomLeft.y > topRight.y):\n",
    "            return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "            return 0\n",
    "\n",
    "        # 如果矩形代表一个点，则定位了一艘船\n",
    "        if (topRight.x == bottomLeft.x) and (topRight.y == bottomLeft.y):\n",
    "            return 1\n",
    "\n",
    "        # 递归地检查 4 个子矩形中的船\n",
    "        mid_x = (topRight.x + bottomLeft.x) // 2\n",
    "        mid_y = (topRight.y + bottomLeft.y) // 2\n",
    "        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \\\n",
    "               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \\\n",
    "               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "      def dfs(topRight, bottomLeft):\n",
    "        x1, y1 = bottomLeft.x, bottomLeft.y\n",
    "        x2, y2 = topRight.x, topRight.y\n",
    "        if x1 > x2 or y1 > y2:\n",
    "          return 0\n",
    "        if not sea.hasShips(topRight, bottomLeft):\n",
    "          return 0\n",
    "        if x1 == x2 and y1 == y2:\n",
    "          return 1\n",
    "        midx = (x1 + x2) >> 1\n",
    "        midy = (y1 + y2) >> 1\n",
    "        a = dfs(topRight, Point(midx + 1, midy + 1))\n",
    "        b = dfs(Point(midx, y2), Point(x1, midy + 1))\n",
    "        c = dfs(Point(midx, midy), bottomLeft)\n",
    "        d = dfs(Point(x2, midy), Point(midx + 1, y1))\n",
    "        return a + b + c + d\n",
    "      \n",
    "      return dfs(topRight, bottomLeft)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Sea's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Sea:\n",
    "#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:\n",
    "#\n",
    "#class Point:\n",
    "#\tdef __init__(self, x: int, y: int):\n",
    "#\t\tself.x = x\n",
    "#\t\tself.y = y\n",
    "\n",
    "class Solution:\n",
    "    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:\n",
    "        def dfs(topRight, bottomLeft):\n",
    "            x1, y1 = bottomLeft.x, bottomLeft.y\n",
    "            x2, y2 = topRight.x, topRight.y\n",
    "            if x1 > x2 or y1 > y2:\n",
    "                return 0\n",
    "            if not sea.hasShips(topRight, bottomLeft):\n",
    "                return 0\n",
    "            if x1 == x2 and y1 == y2:\n",
    "                return 1\n",
    "            midx = (x1 + x2) >> 1\n",
    "            midy = (y1 + y2) >> 1\n",
    "            a = dfs(topRight, Point(midx + 1, midy + 1))\n",
    "            b = dfs(Point(midx, y2), Point(x1, midy + 1))\n",
    "            c = dfs(Point(midx, midy), bottomLeft)\n",
    "            d = dfs(Point(x2, midy), Point(midx + 1, y1))\n",
    "            return a + b + c + d\n",
    "\n",
    "        return dfs(topRight, bottomLeft)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
